package com.czh.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 栈操作：一种遵循先入后出逻辑的线性数据结构
 *
 * @author chenzhihua
 * @Date 2024/2/20
 */
public class BaseOperateStack {
    public static void main(String[] args) {
        // 1. 使用java自带的栈操作
        System.out.println("使用java自带的栈操作===");
        javaStack();
        // 2. 使用链表实现一个栈操作
        System.out.println("使用链表实现一个栈操作===");
        ListNodeStack();
        // 3. 使用数组实现一个栈操作
        System.out.println("使用数组实现一个栈操作===");
        ArrayStack();
    }

    /**
     * 1. java自带的栈操作
     */
    private static void javaStack() {
        Stack<Integer> stack = new Stack<>();
        // 1. 入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        // 2. 获取栈顶元素 4
        Integer peek = stack.peek();
        System.out.printf("栈顶元素是: %d\n", peek);
        // 3. 出栈
        Integer pop = stack.pop();
        System.out.printf("出栈元素是: %d\n", pop);
        // 4. 获取栈长度
        int size = stack.size();
        System.out.printf("栈元素长度: %d\n", size);
        // 5. 判断是否是空栈
        boolean empty = stack.isEmpty();
        System.out.println("栈元素是否为空:" + empty);
    }

    // 2. 使用链表实现一个栈操作
    public static void ListNodeStack() {
        ListNodeStack listNodeStack = new ListNodeStack();
        //1. 入栈
        listNodeStack.push(1);
        listNodeStack.push(2);
        listNodeStack.push(3);
        listNodeStack.push(4);
        listNodeStack.push(5);
        //2. 获取栈顶元素
        int peek = listNodeStack.peek();
        System.out.printf("栈顶元素是: %d\n", peek);
        // 3. 出栈
        int pop = listNodeStack.pop();
        System.out.printf("出栈元素是: %d\n", pop);
        // 4. 获取栈长度
        int size = listNodeStack.size();
        System.out.printf("栈元素长度: %d\n", size);
        // 5. 判断是否是空栈
        boolean empty = listNodeStack.isEmpty();
        System.out.println("栈元素是否为空:" + empty);
    }

    // 3. 使用数组/列表实现一个栈操作
    public static void ArrayStack() {
        ArrayStack arrayStack = new ArrayStack();
        //1. 入栈
        arrayStack.push(1);
        arrayStack.push(2);
        arrayStack.push(3);
        arrayStack.push(4);
        arrayStack.push(5);
        //2. 获取栈顶元素
        int peek = arrayStack.peek();
        System.out.printf("栈顶元素是: %d\n", peek);
        // 3. 出栈
        int pop = arrayStack.pop();
        System.out.printf("出栈元素是: %d\n", pop);
        // 4. 获取栈长度
        int size = arrayStack.size();
        System.out.printf("栈元素长度: %d\n", size);
        // 5. 判断是否是空栈
        boolean empty = arrayStack.isEmpty();
        System.out.println("栈元素是否为空:" + empty);
    }
}

/* 基于链表实现的栈 */
class ListNodeStack {
    ListNode linkStack;
    int size = 0;

    // 入栈-->头插法
    public void push(int val) {
        ListNode listNode = new ListNode(val);
        listNode.next = linkStack;
        linkStack = listNode;
        size++;
    }

    // 出栈
    public int pop() {
        // 先获取栈顶元素
        int peek = peek();
        // 去除栈顶元素
        linkStack = linkStack.next;
        size--;
        return peek;
    }

    // 获取栈顶元素
    public int peek() {
        return linkStack.val;
    }

    // 获取栈长度
    public int size() {
        return size;
    }

    // 判读栈是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}

// 定义一个链表节点
class ListNode {
    int val;
    ListNode next;

    // 构造函数
    public ListNode(int val) {
        this.val = val;
    }

    public ListNode() {
    }
}

/* 基于数组实现的栈 */
class ArrayStack {
    List<Integer> listStack = new ArrayList<>();

    // 1. 入栈
    public void push(int num) {
        listStack.add(num);
    }

    // 2.获取栈顶元素
    public int peek() {
        return listStack.get(listStack.size() - 1);
    }

    // 3. 出栈
    public int pop() {
        return listStack.remove(listStack.size() - 1);
    }

    // 4. 获取栈长度
    public int size() {
        return listStack.size();
    }

    // 5. 判断是否是空栈
    public boolean isEmpty() {
        return size() == 0;
    }
}